package com.zwj.interview.二叉树之使用两个队列;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 输入一棵二叉树，请找出二叉树中每层的最大值
 */
public class 二叉树每一层的最大值II {

    /**
     * 把不同层的节点放入不同的队列中。需要注意的是，当遍历某一层时，
     * 会将位于下一层的子节点也插入队列中，也就是说，队列中会有位于两层的节点。
     * 可以用两个不同的队列queue1和queue2分别存放两层的节点，队列queue1中只放当前遍历层的节点，而队列queue2中只放下一层的节点
     *
     * @param root
     * @return 最开始时把二叉树的根节点放入队列queue1中。接下来每次从队列中取出一个节点遍历。
     * 由于队列queue1用来存放当前遍历层的节点，因此总是从队列queue1中取出节点用来遍历。
     * 如果当前遍历的节点有子节点，并且子节点位于下一层，则把子节点都放入队列queue2中
     * <p>
     * <p>
     * 当队列queue1被清空时，当前层的所有节点都已经被遍历完。通过比较这一层所有节点的值，
     * 就能找出这一层所有节点的最大值。在开始遍历下一层之前，把队列queue1指向队列queue2，
     * 并将队列queue2重新初始化为空的队列。重复这个过程，直到所有节点都遍历完为止
     */
    public List<Integer> largestValues(TreeNode root) {
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        if (root != null) {
            queue1.offer(root);
        }
        List<Integer> result = new LinkedList<>();
        int max = Integer.MIN_VALUE;
        while (!queue1.isEmpty()) {
            TreeNode node = queue1.poll();
            max = Math.max(max, node.val);
            if (node.left != null) {
                queue2.offer(node.left);
            }
            if (node.right != null) {
                queue2.offer(node.right);
            }
            //一个队列为空的时候,表示这一层就遍历完了。就将该层的最大值放到结果集中，同时将queue2赋值给queue1,queue2重新new一个
            if (queue1.isEmpty()) {
                //找到了这一层的最大值了
                result.add(max);
                //重置max
                max = Integer.MIN_VALUE;
                queue1 = queue2;
                queue2 = new LinkedList<>();
            }
        }
        return result;
    }






}
